/*
 * Arrays.cpp
 * This program sets up an array of 5 ints and does a brute force sort
 *  by trying all 5! permutations of ordering the 5 elements of the array
 *  and checking each one to see if it is sorted.
 *
 *  Created on: Feb 7, 2014
 *      Author: Anthony Varghese
 *
 */
#include <iostream>

using namespace std;

// Utility functions that work on arrays:

bool check(const int array[], int size); // check if array is sorted
void copy(int destination[], int source[], const int ); // make a copy of the source in the destination
void rotate(int array[], const int start, const int n); // rotate the elements of the array from start index to n-1


int main(){
	const int ARRAY_SIZE = 5;
    int start[ARRAY_SIZE];

    // Set the elements of the array to anything - pick random values
    start[0] = 1002;
    start[1] =   23;
    start[2] =   -1;
    start[3] =  -45;
    start[4] =  548;

    cout << "Here is the start array:" << endl;
    for (int i=0; i<ARRAY_SIZE; i++)
    	cout << " " << start[i];
    cout << endl << endl;


    // Make a copy of the original array
    int b[ARRAY_SIZE];
    copy(b, start, ARRAY_SIZE);
    for (int i=0; i<ARRAY_SIZE; i++){
        int c[ARRAY_SIZE];
        copy(c, b, ARRAY_SIZE);
        for (int j=0; j<ARRAY_SIZE-1; j++){
            int d[ARRAY_SIZE];
            copy(d, c, ARRAY_SIZE);
            for (int k=0; k<ARRAY_SIZE-2; k++){
                int e[ARRAY_SIZE];
                copy(e, d, ARRAY_SIZE);
                for (int il=0; il<ARRAY_SIZE-3; il++){
                    int f[ARRAY_SIZE];
                    copy(f, e, ARRAY_SIZE);

                    /*
                     * Print out the current permutation and check if it is sorted
                     */
                    cout << "  Test array: ";
                    for (int i=0; i<ARRAY_SIZE; i++)
                    	cout << " " << f[i];
                    bool sorted = check( f, ARRAY_SIZE );
                    if (sorted)
                    	cout << " - The array is sorted!!" << endl;
                    else
                    	cout << " - The array is not sorted." << endl;

                    // Rotate the last two elements of the array
                	rotate( e, 3, ARRAY_SIZE);
                }
                // Rotate the last three elements of the array
            	rotate( d, 2, ARRAY_SIZE);
            }
            // Rotate the last four elements of the array
        	rotate( c, 1, ARRAY_SIZE);
        }
        // Rotate the entire array
    	rotate( b, 0, ARRAY_SIZE);
    }
	cout << "Done!" << endl;
}


bool check(const int array[], int size){
	for (int i=1; i<size; i++)
		if (array[i] < array[i-1])
			return false;
	return true;
}

void copy( int destination[], int source[], const int n){
	for (int i=0; i<n; i++)
		destination[i] = source[i];
}

void rotate(int array[], const int start, const int n){
	int temp = array[start];
	for (int i=start; i<n-1; i++)
		array[i] = array[i+1];
	 array[n-1] = temp;
}
